package problems.daily;

import java.util.Arrays;

/**
 * 902. 最大为 N 的数字组合
 * <p>https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/</p>
 *
 * @author habitplus
 * @since 2022/10/18 10:20
 */
public class DT902 {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        if (n < 1) return 0;

        int m = digits.length;
        final int N = 10;
        // 将 digits 转化为整数存储
        int[] nums = new int[m];

        // nums中值到下标的映射
        // 由于 digits 是非递减的，所以也可表示小于或等于 nums[idxMap[i]] 的数量
        int[] idxMap = new int[N];

        int t;

        // 初始化 nums, idxMap
        Arrays.fill(idxMap, -1);
        for (int i = 1, j = 0; i < N; ++i) {
            if (j < m && i == (t = digits[j].charAt(0) - '0')) {
                nums[j] = t;
                idxMap[t] = j;
                ++j;
            } else {
                idxMap[i] = idxMap[i-1];
            }
        }


        char[] chs = String.valueOf(n).toCharArray();
        n = chs.length;
        // 标记高位是否溢出
        boolean ex = false;
        int ret = 0;

        for (int i = 0; !ex && i < n; ++i) {
            t = chs[i] - '0';
            // 当前数位小于 nums 中的最小数字
            if (idxMap[t] < 0) break;

            // 当前数位大于对应 nums 中的数字
            // 当前数位已经是最后一位
            if (t > nums[idxMap[t]] || i == n - 1) {
                ex = true;
                ret += (idxMap[t] + 1) * (int) Math.pow(m, n - 1 - i);
            } else {
                ret += idxMap[t] > 0 ? idxMap[t] * (int) Math.pow(m, n - 1 - i) : 0;
            }
        }

        int mul = 1;
        for (int i = 1; i < n; ++i) {
            mul *= m;
            ret += mul;
        }

        return ret;
    }

    public static void main(String[] args) {
        System.out.println(new DT902().atMostNGivenDigitSet(new String[] {"3","4","5","6"}, 64));
        System.out.println((int) Math.pow(4, 1));
    }
}
